public class Test {


    //字符串相乘
    public String multiply(String num1,String num2){
        int m = num1.length(),n = num2.length();
        char[] n1 = new StringBuffer(num1).reverse().toString().toCharArray();
        char[] n2 = new StringBuffer(num2).reverse().toString().toCharArray();

        int[] tmp = new int[m+n-1];

        //无进位相乘后相加
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                tmp[i+j] += (n1[i]-'0') * (n2[j]-'0');
            }
        }

        //处理进位
        int cur = 0,t =0;
        StringBuffer ret = new StringBuffer();
        while (cur<m+n-1 || t!=0){
            if (cur<m+n-1) t+=tmp[cur++];
            ret.append((char)(t%10+'0'));
            t/=10;
        }

        //处理前缀0
        while (ret.length()>1 && ret.charAt(ret.length()-1) == '0'){
            ret.deleteCharAt(ret.length()-1);
        }

        return ret.reverse().toString();

    }



    //二进制求和
    public String addBinary(String a,String b){
        StringBuffer ret = new StringBuffer();
        int cur1 = a.length()-1, cur2 = b.length()-1;
        int t = 0;
        while(cur1>=0 || cur2>=0 || t!=0){
            if (cur1 >= 0) t += a.charAt(cur1--)-'0';
            if (cur2 >= 0) t += b.charAt(cur2--)-'0';
            ret.append((char)('0'+ (char)(t%2)));
            t/=2;
        }
        ret.reverse();//把字符串逆转回来
        return ret.toString();
    }



    //最长回文之串
    public String longestPalindrome(String s){
        int begin = 0,len = 0,n = s.length();
        for (int i = 0; i < n; i++) {
            //奇数个的情况
            int left = i,right = i;
            while(left>=0 && right<=n && s.charAt(left)== s.charAt(right)){
                left--;right++;
            }
            if (right-left-1 > len){
                len = right-left-1;
                begin = left+1;
            }
            //偶数个的情况
            left = i;right= i+1;
            while(left>=0 && right<=n && s.charAt(left)== s.charAt(right)){
                left--;right++;
            }
            if (right-left-1 > len){
                len = right-left-1;
                begin = left+1;
            }
        }
        return s.substring(begin,begin+len);
    }



    //最长公共前缀
    public String longestCommonPrefix(String[] strs){
        //解法一：两两比较
//        String ret = strs[0];
//        for (int i = 1; i < strs.length; i++) {
//            ret = findCommon(strs[i],ret);
//        }
//        return ret;

        //解法二：统一比较
        for (int i = 0; i < strs[0].length(); i++) {
            char tmp = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {
                if (i == strs[j].length() || strs[j].charAt(i) != tmp) return strs[0].substring(0,i);
            }
        }
        return strs[0];
    }
    public String findCommon(String s1,String s2){
        int i = 0;
        while(i<Math.min(s1.length(),s2.length()) && s1.charAt(i) == s2.charAt(i)) i++;

        return s1.substring(0,i);
    }
}
